#pragma once
// 栈 可以用vector，list去适配
// 但是队列 vector不能适配，因为插入删除效率低 。list可以

// 优先级队列 里面有一些堆的调整

namespace myqueue
{
    // queue模拟实现
    template <class T, class Container = deque<T>>
    class queue
    {
    public:
        void push(const T &x)
        {
            _con.push_back(x);
        }
        void pop()
        {
            _con.pop_front();
        }
        const T &front()
        {
            return _con.front();
        }
        const T &back()
        {
            return _con.back();
        }

        size_t size()
        {
            return _con.size();
        }
        bool empty()
        {
            return _con.empty();
        }

    private:
        Container _con;
    };
    // deque（双端队列）支持常数时间复杂度的头部和尾部插入和删除操作，非常适合作为队列的底层容器。
    // 与vector相比，deque在头部插入和删除操作的效率更高，因为vector的头部插入和删除操作需要移动所有元素。

    // 优先级队列模拟实现
    // priority_queue
    // 优先队列是一种特殊的队列，它在每次 pop 操作时，总是移除并返回优先级最高的元素。下面我将详细讲解这个代码的每一行。
    // 堆性质：最大堆（或最小堆）是一棵完全二叉树，其中每个节点的值都大于或等于其子节点的值。
    // adjust_up 和 adjust_down 函数用于维护堆性质。插入新元素后，需要向上调整；移除堆顶元素后，需要向下调整。
    // 容器适配器：优先队列是通过适配容器（如 vector）来实现的。容器提供了存储和基本操作，而适配器提供了优先队列的特性。
    template <class T, class Container = vector<T>>
    class priority_queue
    {
    public:
        void adjust_up(int child)
        {
            int parent = (child - 1) / 2;
            while (child > 0)
            {
                if (_con[child] > _con[parent])
                {
                    swap(_con[child], _con[parent]);
                    child = parent;
                    arent = (child - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }
        // 难理解
        void adjust_down(int parent)
        {
            int child = parent * 2 + 1;

            while (child < _con.size())
            {
                if (child + 1 < _con.size() && _con[child + 1] > _con[child])
                {
                    ++child;
                }

                if (_con[child] > _con[parent])
                {
                    swap(_con[child], _con[parent]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                {
                    break;
                }
            }
        }

        void push(const T &x)
        {
            _con.push_back(x);
            adjust_up(_con.size() - 1);
        }
        void pop()
        {
            swap(_con[0], _con[_con.size() - 1]);
            _con.pop_back();

            adjust_down(0);
        }

        const T &top()
        {
            return _con[0];
        }

        size_t size()
        {
            return _con.size();
        }

        bool empty()
        {
            return _con.empty();
        }

    private:
        Container _con;
    };

}